#include<iostream>
using namespace std;
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};

class Solution {
private:
    Node* flattenCore(Node* head) {
        Node* prev = NULL;
        while (head != NULL) {
            Node* node=NULL;
            prev = head;
            Node* next = head->next;
            if (head->child != NULL) {
                node = flattenCore(head->child);
                head->next = head->child;
                head->child->prev = head;
                head->child = NULL;
                node->next = next;
                if (next != NULL)
                    next->prev = node;
                prev = node;
            }
            head = next;
        }
        return prev;
    }
public:
    Node* flatten(Node* head) {
        if (head == NULL)
            return head;
        flattenCore(head);
        return head;
    }
};